# Sudoku Solver
# Tamara Roberson <tamara.roberson@gmail.com>
# Based on code from sfabriz.
# For detailed explanation, see:
#   http://www.osix.net/modules/article/?id=792

namespace SudokuSolver

import System
import System.Collections
import System.Collections.Specialized
import System.Diagnostics
import System.Text
import Mono.Unix

import ZoeTools.Algorithms.DancingLinks
import ZoeTools.Objects.LinkedMatrix


class SudokuSolveDLX (DLXMatrix):
"""
<remarks>
Constraints: 
4 columns group: <r,c> <d,r> <d,c> <d,b>
1 : r * dim + c
2 : (1 * dim * dim) + r * dim + d = dim * (1 * r + dim) + d
3 : (2 * dim * dim) + c * dim + d = dim * (2 * dim + c) + d
4 : (3 * dim * dim) + b * dim + d = dim * (3 * dim + b) + d
--------------------------------------------------
Retrieving row informations
row = r * dim * dim + c * dim + d
d = row % dim
c = (row / dim) % dim
r = row / (dim * dim)
--------------------------------------------------
In general, we have to pay attention to the fact 
that r, c and d are in [0-8] but in a real sudoku
the numbers are in [1-9].
This leads to a simple conversion in 2 places.
In the SetStartingGrid method we have:

SelectRow ( r * dim * dim + c * dim + (grid[r,c] - 1));

and in the PrintSolution method we have:

Console.Write((s[i*dim+j]+1).ToString().PadRight(2));
---------------------------------------------------
To solve a sudoku:
SudokuSolveDLX sdlx=new SudokuSolveDLX(dim);
sdlx.BuildSudokuMatrix();
sdlx.SetStartingGrid(...);
sdlx.SolveSudoku(...);
sdlx.UnselectAllRows();
</remarks>
"""
	_ = Catalog.GetString

	# Variables
	[Property (Dim)]
	_dim  as int
	"""<summary>Dimension of the sudoku grid</summary>"""

	_block_dim as int
	"""<summary>Single block dimension</summary>"""


	# Constructor
	def constructor ([required (dim >= 1)] dim as int):
		_dim = dim
		_block_dim = Math.Sqrt (dim)


	# Methods
	# Methods :: Public
	# Methods :: Public :: BuildSudokuMatrix
	def BuildSudokuMatrix ():
	"""
	<summary>Builds the sudoku matrix.</summary>
	<remarks>Calls DLX.BuildSkeleton and sets the _dim**3 rows</remarks>
	"""
		# skeleton first
		super.BuildSkeleton (_dim**3, 4*_dim**2)

		# appending all the rows then
		block = 0

		for row in range (0, _dim):
			for col in range (0, _dim):
				# set the block
				block  = row / _block_dim
				block *= _block_dim 
				block += col / _block_dim
	
				for cur_dim in range (0, _dim):
					pos = CalcRowPositions (row, col, block, cur_dim)
					AppendRow (pos, row, col, cur_dim)


	# Methods :: Public :: SetStartingGrid (grid as (string))
	def SetStartingGrid ([required] grid_str as (string)):
	"""
	<summary>Selects the givens in the sudoku matrix.</summary>
	<param name="grid">The grid of givens (e.g. ["123456789",
	  "321654987", ...])</param>"""
		grid = matrix (int, _dim, _dim)

		for row in range (0, _dim):
			for col in range (0, _dim):
				cell = grid_str[row][col].ToString ()
				grid[row,col] = int.Parse (cell)

		SetStartingGrid (grid)


	# Methods :: Public :: SetStartingGrid (int[,])
	def SetStartingGrid ([required] grid as (int, 2)):
	"""
	<summary>Selects the givens in the sudoku matrix.</summary>
	<param name="grid">The grid of givens</param>
	"""
		for row in range (0, _dim):
			for col in range (0, _dim):
				SelectRow (grid, row, col)


	# Methods :: Public :: SolveSudoku
	def SolveSudoku ():
	"""
	<summary>Solves the sudoku</summary>
	<param name="sm">The method used to solve the sudoku</param>
	<returns>True if a unique solution is found</returns>
	"""
		super.TotSolutions = 0 
		Solve ()
		super.UnselectAllRows ()
		return (super.TotSolutions == 1)


	# Methods :: Private
	# Methods :: Private :: AppendRow
	private def AppendRow (
	  [required] pos as (int),
	  [required (r >= 0)] r as int,
	  [required (c >= 0)] c as int,
	  [required (d >= 0)] d as int):
		super.AppendRow (pos, r * _dim**2 + c * _dim + d)
	
	# Methods :: Private :: CalcRowPositions
	private def CalcRowPositions (
	  [required (row   >= 0)] row as int,
	  [required (col   >= 0)] col as int,
	  [required (block >= 0)] block as int,
	  [required (cur_dim >= 0)] cur_dim as int):
		pos = array (int, 4)
		pos[0] = row * _dim + col
		pos[1] = _dim * (row   + 1 * _dim) + cur_dim
		pos[2] = _dim * (col   + 2 * _dim) + cur_dim
		pos[3] = _dim * (block + 3 * _dim) + cur_dim
		return pos


	# Methods :: Private :: SelectRow
	private def SelectRow (
	  [required] grid as (int, 2),
	  [required (row >= 0)] row as int,
	  [required (col >= 0)] col as int):
		return if (grid[row,col] == 0)
		idx  = row * _dim**2
		idx += col * _dim
		idx += grid[row,col] - 1
		super.SelectRow (idx)

